package com.yuan.algorithms.arithmetic_1;

import java.util.Scanner;


/*
 * 接收一串由圆括号、方括号、花括号组成的字符串，它们之间可以相互嵌套，
 * 如{([])}{[]}是正确的格式，而{([)]}是不正确的格式。
 * 你需要对接收的括号进行格式判断，如果合法就输出Yes，否则输出No。
 * 
 * 分析：可以使用堆栈对括号进行存储匹配，若匹配成功一对括号，便出栈，最后，堆栈为空则括号串合法。
 */

public class 堆栈_括号匹配问题 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String str = sc.next();
			if (bracketMatch(str)) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}

	public static boolean bracketMatch(String str) {
		StackSLinked sl = new StackSLinked();
		for (int i = 0; i < str.length(); i++) {
			char a = str.charAt(i);
			switch (a) {
			case '{':
			case '[':
			case '(':
				sl.push(a);
				break;
			case '}':
				if (!sl.isEmpty() && (char) sl.pop() == '{') {
					break;
				} else {
					return false;
				}
			case ']':
				if (!sl.isEmpty() && (char) sl.pop() == '[') {
					break;
				} else {
					return false;
				}
			case ')':
				if (!sl.isEmpty() && (char) sl.pop() == '(') {
					break;
				} else {
					return false;
				}
			default://不是括号，返回false
				return false;
			}
		}
		return sl.isEmpty();//匹配结束后，获取堆栈的长度，为空则全部匹配成功，字符串合法
	}

}
